2nd International Olympiad in Informatics 

MINSK,BYELLORUSSIA, 1990 



Round 1. 

 

PROBLEM 1. 

Program the process transforming figure arrangement in A 

into that in B. A figure in a cell can be transferred 

into any one of neighbouring empty cells; in the case of 

such transformations the cell previously occupied by the 

figure becomes empty. 

+----+----+----+----+ 

|  7 |  3 |  5 | 14 | 

+----+----+----+----+ 

|    |  4 |  9 | 13 | 

+----+----+----+----+  --------> 

|  1 |    |  2 | 10 | 

+----+----+----+----+ 

| 11 |  8 | 12 |  6 | 

+----+----+----+----+ 

          A 

		+----+----+----+----+ 

		|  1 |  2 |  3 |  4 | 

		+----+----+----+----+ 

		|  5 |  6 |  7 |  8 | 

		+----+----+----+----+ 

		|  9 | 10 | 11 | 12 | 

		+----+----+----+----+ 

		| 13 | 14 |    |    | 

		+----+----+----+----+ 

		          B 

 

 

PROBLEM 2. 

The game of "BOXES" involves players joining dots in a 

gird one at a time. The player who completes a box scores 

a point and is entitled to another turn. The end of the 

game is when the grid has been completed with the winner 

naturally being the one with the more points. Only 

vertical and horizontal lines filling the space between 

two points are allowed. 

The example below shows a game between Red and Blue which 

is half completed: 

o----o    o----o----o 

|    |    |    |    | 

o----o----o----o----o 

|         | 

o    o    o    o----o 

| 

o----o    o----o    o 

     |              | 

o    o    o    o----o 

This can be represented with R & B showing lines filled 

by Red and Blue with O indicating a 'vacant' line: 







  R    O    B    R 

B    R    B    B    B 

  B    B    R    R 

R    O    R    O    O 

  O    O    O    B 

B    O    O    O    O 

  B    O    R    O 

O    R    O    O    R 

  O    O    O    B 

This is then condensed to produce the matrix shown below: 

ROBR 

BRBBB 

BBRR 

ROROO 

OOOB 

BOOOO 

BORO 

OROOR 

OOOB 

1. Write a program which scans a matrix of the type shown 

  above (which will ALWAYS represented a 5 x 5 point grid) 

  and determines the number of 3- sided boxes (of ANY 

  orientation). Data should be read from a single file as a 

  series of 9r lines representing r games which is 

  terminated by the word END starting a separate line. Your 

  program should output a one line message for each matrix 

  in the data: 

  MATRIX r contained x 3-sided box(es). 

2. Modify your answer to Part 1 to continue a single game 

  on behalf of Blue. Complete as many boxes as the single 

  move allows (bearing in mind that a complete box means 

  another move). The final move is irrelevant but should 

  NOT result in a 3-sided box unless forced to do so. 

  Your program should return: 

  x boxes have been completed. Final move = L, C where L & 

  C are the Line and Column representing the character in 

  the matrix and x should be the number NEW boxes which 

  have been formed, but NOT the total number of complete 

  boxes in the grid. 

 

 

*** PROBLEM 3. 

There are N books and two readers, A and B, wanting to 

read these books. Nonnegative integers A[I] and B[I] are 

given such as reader A (or B) needs A[I] (or B[I], 

respectively) hours to read book I, 1<=I<=N. Both the 

readers begin reading at time 0. At any time each reader 

is allowed to read at most one book and both readers 

cannot read the same book. 

Integer K, 2<=K<=N, is given and the books are supposed 

to be numbered in such a way that no reader can start 

reading book J, 2<=J<=K, until book J-1 is read by both 

the readers. 

The order of reading the other books is immaterial for 

each reader and may be arbitrary. 

Preemptions are allowed in the process of reading any 

book by any reader. It means that this process may be 

interrupted at any integer time and be resumed lately 

starting from the point of interruption. In between 

interruption and resumption of the process of reading the 

book a reader may read any other book he has not 

completed and has the right to read it. 

IT IS NECESSARY: 

1. To organize inputting the data in the form: 

  < ENTER  N -->  > 

  < ENTER  K -->  > 

  < ENTER: > 

  < A[1] --> >  < B[1] --> > 

  < A[2] --> >  < B[2] --> > 

  .......................... 

  < A[N] --> >  < B[N] --> > 

2. To find the largest possible time T before which all 

  the books cannot be read by both the readers; to output 

  calculated value of T. 

3. To build a schedule of reading the books by each 

  reader which meets all the restrictions listed above and 

  under which the process of reading all the books 

  terminates at time T. The schedule for each reader is to 

  be written in the form. 

     < SCHEDULE FOR READER A ( or B ) > 

  < Book >  < Start > < Finish > 

    .....     .....     ..... 

    .....     .....     ..... 

  In the tables of the above form all the time intervals 

  within which reader A (or B) is reading a book and the 

  number of this book should be mentioned. 

4. Output the number of preemptions of each reader. Try 

  to reduce the number of preemptions for each reader. 

 

 

PROBLEM 4. 

It's given integer number K. 

A strip of paper is divided into N cells (K<=N<=40). Two 

players choose and cross out K empty adjacent cells one 

by one. The winner is the one who has made the last move. 

  1    2                             N 

+----+----+----+----+-        -----+----+ 

|    |    |    |    |   . . .      |    | 

+----+----+----+----+-        -----+----+ 

1. Input N and define, whether player 1 has winning 

  strategy (i.e. whether he can win under the best 

  following moves of player 2). Print message "Player 1 has 

  winning strategy" or "Player 1 doesn't have winning 

  strategy". 

2. Define for given N, if player 1 has winning strategy, 

  if his 1st move is entered into the computer from 

  keyboard. 

3. Make the game for given (paragraph 1 and 2) N and 

  player's 1 first move. Programme plays for player 2. 

  Moves of player 1 are entered from the keyboard. 

  Move is given by index of cell L (1<=L<=N-K+1). Cells 

  from L till L+K-1 are crossed out while doing this. After 

  each move current position of the game is printed out in 

  the form of: 

  1  2*  3*  ...  N 

  Index number is printed upside, crossed out cells are 

  marked by symbols '*'. 

  You must print 'Victory of Player 1 (Player 2)' when the 

  game is over. Entering N and K print message 'N>' and 

  'K>'. 

  Entering move print 'Move of Player 1>'. 

  Foresee the control of correctness of input data. 

 

 

PROBLEM 5. 

  [ PROLAN/M ] 

Suppose that the NePhihhan hardware company has developed 

a new RISC micro-processor capable to handle a single 

data type - string of characters - and to perform a 

single operation on them-context-sensitive replacement 

(searching a given substring in a string and replacing it 

by another substring). Two memory areas are used, one of 

each contains the program (a list of discriptions of the 

possible replacements), while the other one (we will call 

it R; its size is supposed to be virtually unlimited) is 

used to store the input data, the intermediary results 

and the final output. 

The programs for the processor are written in a language 

which we will call PROLAN/M. Before we describe it 

formally, we will give an example of a program: 

(aa,b) (ba,a) (bc,a) (c,start) (d,) (b,finish) (,) 

When executed string     abcabcd 

as input, the programs yields the string     finish 

as a final value, while the contents of R goes through 

the values 

     abcabcd, aaabcd, babcd, abcd, aad, db, b, finish 

successively. 

Now to the formal description of the syntax of PROLAN/M 

(we use "::=" to denote "is defined as" and ":" to denote 

"or"): 

<'PROLAN/M'-program>     ::=  <substitut.sequence>(,) 

<substitut.sequence>     ::=  <substitution>: 

     ::=  <substitut.sequence><substitution> 

<substitution> ::=  (<left part>,<right part>) 

<left-hand part>    ::=  <string> 

<right-hand part>   ::=  <string>:<empty> 

<string>  ::=  <string symbol>:<string><string symbol> 

<empty string> ::= 

<string symbol>     ::=  <any ASCII character except ',' 

, ')' > 

After the input string has been loaded into R, the 

program is executed in the following way: the processor 

looks for the first <substitution> in the 

<substitut.sequence> for which the <left-hand part> is a 

substring of the string in R. If the search is 

successful, the <right-hand part> of the same 

<substitution> replaces the corresponding substring in R 

(the leftmost one if not unique). This procedure is then 

repeated from the beginning with the new R-value until mo 

<left-hand part> in the <'PROLAN/M'-program> is found as 

a substring in a current value R, which is then 

considered to be the final result, and the execution is 

aborted. 

--------------------------------------------------------- 

Problem 1. 

  Write and debug a PROLAN/M program that converts a string 

  of the type 

  <nat.nr1>+<nat.nr2>=? 

  (<nat.nr1> and <nat.nr2> are sequences of decimal digits 

  representing natural numbers) to a string of the type 

  <nat.nr1>+<nat.nr2>=<nat.nr3> 

  containing a mathematically correct statement (<nat.nr1> 

  and <nat.nr2> are the same). For example, the string 

  1990+123=? 

  should be transformed into 

  1990+123=2113 

  at the end of the execution. Store your program in a file 

  named SUM.PRM. 

Problem 2. 

  Write a PROLAN/M debugger. It should able to do the 

  following: 

  (a) request the name of a text file containing the 

    PROLAN/M program; 

  (b) request the initial contents of R; 

  (c) perform the transformations of the input string 

    according to the program in the file; 

  (d) display the result on the screen; 

  (e) it is desirable to enable a tracing mode. 

--------------------------------------------------------- 

Your grade for P.1 will depend on the number of 

<substitutions>s in the <substitution sequence>, as well 

as on the speed at which the tests which will be given by 

the jury will be performed. Therefore you may wish to 

hand in two versions of the program, each of which will 

be better at satisfying a different criterion. 

The program from P.1 will be tested using a programming 

system designed by the jury for this special purpose. 

Your grade for P.2 will depend on passing the jury's test 

and on your having implemented all the subproblems. 

 

 

PROBLEM 6. 

Given integers a and n (n<100). Suppose an imaginary 

programming language containing an assignment statement 

and a multiplication operator. Write a program that 

generates a text in that language for computation of 

b=a^n, with minimal number of multiplications. An example 

of generated text for n=13, where each pair of brackets 

{} contains comments, is presented below: 

X1:=a;    {=a} 

X2:=X1*X1;     {=a^2} 

X3:=X2*X2;     {=a^4} 

X4:=X3*X1;     {=a^5} 

X5:=X3*X3;     {=a^8} 

X6:=X5*X4;     {=a^13} 

b:=X6; 

 

********************************************************* 





2nd International Olympiad in Informatics 

MINSK, 1990 

Round 2. 

 

 

PROBLEM 1. 

Each watchman in a certain art gallery is on duty during 

some continuous time period. The Guard Schedule is 

defined to be a set of pairs [T1(i),T2(i)] - the starting 

and the ending times of the i'th watchman's duty. Given a 

Guard Schedule you are required: 

(a) To check whether there are at least two watchman in 

  the gallery at each moment of the period [0, EndTime]. 

  If the condition (a) is not fulfilled, 

(b) Determine all the periods when the guard is 

  insufficient (less then two watchmen on duty). 

(c) Find the minimal number of additional watchmen with 

  duties of a prescribed equal length needed to obtain a 

  valid Guard Schedule, i.e. one with condition (a) 

  fulfilled. 

INPUT: 

 (All times are given in integer minutes.) 

 EndTime   -    the time when the guard is over, i.e. the 

   gallery should be guarded within the period [0, EndTime]. 

 N    -    the number of watchmen. 

 T1[i]. T2[i], i=1, ..., N     -    the starting and the 

   ending times of the i'th watchman's duty. 

 Length    -    the prescribed length of the duty for each 

   additional watchman. 

OUTPUT: 

 (1) The answer for point (a) in the form "Yes/No". 

 (2) If the previous answer is "no", the list of pairs 

 (k,1) - the beginnings and the ends of all time periods 

   with insufficient guard, and the number of watchmen in 

   each (0 or 1). 

 (3) The number of additional watchmen and the list of 

   starting and ending times of every additional watchman's 

   duty. 

 

 

PROBLEM 2. 

N segments are given on the plane by the co-ordinates of 

their endpoints, N>0. Endpoints of segment are specified 

by two pairs (x1[i], y1[i]), and (x2[i], y2[i]), 1<=i<=N. 

The endpoints of any segment are belong to it. 

You are required: 

1. To organize inputting the data in the form kind of 

  <Enter N -- the number of segments :> 

  <Enter co-ordinates of i'th segment:> 

  x1[1]--> y1[1]--> 

  x2[1]--> y2[1]--> 

    :::      ::: 

2. To find a straight line which has common points with 

  as many segments as possible. Any of the common points is 

  allowed to be an endpoint of a segment. To output in 

  increasing order the number of the segments that have 

  common points with found straight line. 

 

 

***PROBLEM 3. 

Nodes numbered by 1, 2, ..., N (N<=50) are connected by a 

network of roads, each of which is of length 1. The roads 

are going at different heights and are intersected at the 

nodes only. At the initial moment 0 there are robots in 

some of the nodes. The total number of the robots is M (M 

= 2 or 3). The robots keep moving continuously from one 

node to another independently and can change the 

direction of their moving at the nodes only. The robots 

are not allowed to stop. The speed of the i'th robot 

equals speed[i] (speed[i] = 1 or 2). The robots are being 

controlled in such way as to minimize the time all of the 

robots need to get together at the same place. 

You are required to find the minimal time T after which 

the meeting of all the robots at the same place can occur 

and to indicate this time T, or else to determine that 

the meeting of all M robots at the same place is 

impossible at any time t>=0. 

The form of the input should be: 

<Input N:> 

<Input number of roads K:> 

<Road 1 connects points:> 

     ... 

<Road K connects points:> 

     (pairs are input as I J) 

<Input number of robots M:> 

<Input speed of robot 1:> 

     ... 

<Input speed of robot M:> 

<Input initial position of robot 1:> 

     ... 

<Input initial position of robot M:> 

     (All numbers above must be non-negative integers.) 

The form of output is 

<Time = ...> 

 





 

PROBLEM 4. 

All streets in a certain rectangular-shaped city situated 

in an uneven area are going either from south to north (N 

streets) or from west to east (M streets), so that the 

city is divided into square blocks with sides equal to 1. 

Every segment of a street enclosed between two 

neighbouring crossings goes either only down or only up, 

or else it may be horizontal. 

Matrix K[y,x] (with dimension MxN) contains the heights 

of the crossings above the sea level. 

     /\ Y 

     | 

M    +---+---+---+---+---+---+ 

     |   |   |   |   |   |   | 

     +---+---+---+---+---+---+ 

.    |   | A |   |   |   |   | 

.    +---+---o---+---+---+---+ 

.    |   |   |   |   |   |   | 

     +---+---+---+---+---+---+ 

     |   |   |   |   | B |   | 

2    +---+---+---+---*---+---+ 

     |   |   |   |   |   |   | 

1    +---+---+---+---+---+---+--------->X 

     1   2      ...          N 

You are required to write a program that: 

1. Inputs dimension of matrix - M and N. 

2. Inputs the matrix elements H[i,j]. i=1,M , j=1,N. 

3. Inputs the coordinates of two crossings - A and B. 

4. Reports the answer to the question whether it is 

  possible to move from A to B or from B to A, going down 

  all the time. 

  If the answer to the question from P.3 proves to be 

  affirmative, the program also 

5. Determines at least one such path and displays the 

  coordinates of the crossings involved on the screen. 

6. Determines all paths of this kind. 

 



